/**
 * File DefaultPrefixTree.java
 * ---------------------------------------------------------
 *
 * Copyright (C) 2012 David Bauske (david.bauske@googlemail.com)
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy of this software and associated documentation files (the "Software"),
 * to deal in the Software without restriction, including without limitation the rights to use, copy, modify, merge, publish, distribute, sublicense,
 * and/or sell copies of the Software, and to permit persons to whom the Software is furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY,
 * WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 */
package net.cl.util.collections;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Iterator;
import java.util.List;
import java.util.Map;
import java.util.Map.Entry;

/**
 * Default implementation of a prefix search tree.
 * <p>
 * Note that this class is immutable.
 * </p>
 * @author David Bauske
 */
public final class DefaultPrefixTree<E> implements PrefixTree<E>
{
	// ----------------------------------------------------------------------
	// Fields
	// ----------------------------------------------------------------------

	private Node<E> 				mRoot;

	// ----------------------------------------------------------------------
	// Public Methods
	// ----------------------------------------------------------------------

	@Override
	public List<E> search(String pInput)
	{
		List<E> result = new ArrayList<E>();

		mRoot.search(pInput, result);

		return result;
	}

	// ----------------------------------------------------------------------
	// Private Methods
	// ----------------------------------------------------------------------

	/**
	 * Intentionally private constructor to force the usage of the builder class.
	 */
	private DefaultPrefixTree()
	{

	}

	// ----------------------------------------------------------------------
	// Inner classes
	// ----------------------------------------------------------------------

	/**
	 * Builder class for a DefaultPrefixTree
	 */
	public static class Builder<E>
	{
		private Node<E> 	mRoot = new Node<E>();

		/**
		 * Creates a new Builder object.
		 */
		public Builder()
		{

		}

		/**
		 * Adds a searchable term to the builder.
		 * @param pTerm The searchable term
		 * @param pElement The element associated with this term.
		 * @return <i>this</i> to allow chaining.
		 */
		public Builder<E> addTerm(String pTerm, E pElement)
		{
			mRoot.addTerm(pTerm, pElement);
			return this;
		}

		/**
		 * Finalizes the search tree construction. note that after this, the
		 * resulting tree cannot be altered any more. The builder object can be
		 * reused, but it will be empty again, just as if it would have been
		 * created right now.
		 * @return The resulting PrefixTree.
		 */
		public DefaultPrefixTree<E> build()
		{
			DefaultPrefixTree<E> tree = new DefaultPrefixTree<E>();
			tree.mRoot = this.mRoot;
			tree.mRoot.optimize();
			this.mRoot = new Node<E>();

			return tree;
		}
	}

	/**
	 * Node structure
	 */
	private static final class Node<E>
	{
		private Map<String, Node<E>>	mNodes = new HashMap<String, Node<E>>();
		private List<E> 				mElements = new ArrayList<E>();

		public void addTerm(String pTerm, E pElement)
		{
			if(pTerm.length() > 0)
			{
				String character = String.valueOf(pTerm.charAt(0));
				String remainder = pTerm.substring(1);

				Node<E> next = mNodes.get(character);
				if(next == null)
				{
					next = new Node<E>();
					mNodes.put(character, next);
				}
				next.addTerm(remainder, pElement);
			}
			else
			{
				// Target node found
				this.mElements.add(pElement);
			}
		}

		public void search(String pInput, List<E> pResult)
		{
			if(pInput.length() > 0)
			{
				for(String key : this.mNodes.keySet())
				{
					if(key.length() > pInput.length() ? key.startsWith(pInput) :
						pInput.startsWith(key))
					{
						String remainder = pInput.substring(Math.min(key.length(),
								pInput.length()));

						Node<E> next = mNodes.get(key);
						if(next != null)
						{
							next.search(remainder, pResult);
						}

						break;
					}
				}
			}
			else
			{
				// Target term found
				addAll(pResult);
			}
		}

		public void addAll(List<E> pResult)
		{
			pResult.addAll(this.mElements);
			for(Node<E> next : this.mNodes.values())
			{
				next.addAll(pResult);
			}
		}

		public void optimize()
		{
			Map<String, Node<E>> tempMap = new HashMap<String, Node<E>>();
			Iterator<Entry<String, Node<E>>> it = this.mNodes.entrySet().iterator();
			while(it.hasNext())
			{
				Entry<String, Node<E>> nextNode = it.next();
				// Only one child node -> nodes can be joined.
				if(nextNode.getValue().mNodes.size() == 1 && nextNode.getValue().mElements.size() == 0)
				{
					Entry<String, Node<E>> afterNextNode = getFirstEntry(nextNode.getValue());
					it.remove();
					nextNode.getValue().mElements.addAll(afterNextNode.getValue().mElements);
					tempMap.put(nextNode.getKey() + afterNextNode.getKey(), afterNextNode.getValue());
				}
			}

			this.mNodes.putAll(tempMap);
			if(tempMap.size() > 0)
			{
				optimize();
			}

			// If merging was not possible, recursively step down
			for(Node<E> node : this.mNodes.values())
			{
				node.optimize();
			}
		}

		private static <E> Entry<String, Node<E>> getFirstEntry(Node<E> pNode)
		{
			return pNode.mNodes.entrySet().iterator().next();
		}

		@Override
		public String toString()
		{
			StringBuilder result = new StringBuilder();
			result.append("[");
			int cnt = 0;
			if(this.mNodes.size() > 0)
			{
				result.append("Children: " + this.mNodes);
				++cnt;
			}

			if(this.mElements.size() > 0)
			{
				if(cnt > 0)
				{
					result.append("; ");
				}
				result.append("Elements: " + this.mElements);
			}
			result.append("]");
			return result.toString();
		}
	}
}
